#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "DemoDateTime.h"

typedef BOOL (*ascendingFunc)(int, int);

void bubbleSort(int* input, int *output, int arrlen, ascendingFunc fp) {
    for (int i=0; i<arrlen; ++i) {
        output[i] = input[i];
    }
    int swap;
    for (int bubbleTop=arrlen; bubbleTop>1; --bubbleTop) {
        for (int i=0; i<bubbleTop-1; ++i) {
            if ((*fp)(output[i], output[i+1])) {
                //swap = output[i];
                //output[i] = output[i+1];
                //output[i+1] = swap;
                // 位运算交换数值
                output[i] = output[i] ^ output[i+1];
                output[i+1] = output[i] ^ output[i+1];
                output[i] = output[i] ^ output[i+1];
            }
        }
    }
}

// 快速排序算法的原理如下：
// 1.从数列中挑出一个元素，称为 “基准”（pivot）;
// 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
// 3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
void quickSortRecur(int *output, int beginIndex, int endIndex, ascendingFunc fp) {
    if (endIndex == beginIndex) {
        return;
    }
    int pivotValue = output[beginIndex];
    int leftIndex = beginIndex;
    int rightIndex = endIndex;
    
    while(rightIndex > leftIndex) {
        while(rightIndex > leftIndex) {
            // 从 endIndex 向 beginIndex 遍历，找到第一个 比 pivotValue 小的，可以移动到 基准 左边的
            // 如果一直没有找到，rightIndex==leftIndex 退出while循环
            if ((*fp)(pivotValue, output[rightIndex])) {
                break;
            }
            --rightIndex;
        }
        
        // rightIndex 下标对应的值 写入 leftIndex, 写入之后，rightIndex 等着被写入
        output[leftIndex] = output[rightIndex];
        ++ leftIndex;
        
        while(rightIndex > leftIndex) {
            // 从 beginIndex 向 endIndex 遍历，找到第一个 比 pivotValue 大的，可以移动到 rightIndex位置
            // 如果一直没有找到，rightIndex==leftIndex 退出while循环
            if ((*fp)(output[leftIndex], pivotValue)) {
                break;
            }
            ++leftIndex;
        }
        
        // leftIndex 下标对应的值 写入 rightIndex, 写入之后，leftIndex 等着被写入
        output[rightIndex] = output[leftIndex];
    }

    //printf("quickSortRecur, begin %d, end %d, pivot %d, pivotValue %d \n", beginIndex,endIndex,leftIndex, pivotValue);

    // pivotValue 写入 leftIndex（== rightIndex）下标
    output[leftIndex] = pivotValue;
    if (leftIndex - beginIndex > 2) {
        quickSortRecur(output, beginIndex, leftIndex-1, fp);
    }
    if  (endIndex - leftIndex > 2) {
        quickSortRecur(output, leftIndex+1, endIndex, fp);
    }
}

void quickSort(int* input, int *output, int arrlen, ascendingFunc fp) {
    for (int i=0; i<arrlen; ++i) {
        output[i] = input[i];
    }
    quickSortRecur(output, 0, arrlen-1, fp);
}


BOOL funcAscend(int left, int right) {
    return left>right;
}

BOOL funcDescend(int left, int right) {
    return left<right;
}

#define SortArrLen (100)

void demoArraySortLogic(void) {
    printf("\ndemoArraySortLogic\n");
    
    srand((int)time(NULL));     //每次执行种子不同，生成不同的随机数
    int a[SortArrLen], b[SortArrLen], c[SortArrLen];
    for (int i=0; i<SortArrLen; ++i){
        a[i] = rand() % 100;
        printf("a%d->%d ",i, a[i]);
    }
    printf("\nsizeof(a)=%lu\n", sizeof(a));

	logWsBegin("冒泡排序 升序 begin\n");
    // 冒泡排序 升序
    //printf("冒泡排序 升序\n");
    bubbleSort(a, b, SortArrLen, funcAscend);
    for (int i=0; i<SortArrLen; ++i){
        printf("c%d->%d ",i, b[i]);
    }
    printf("\nsizeof(b)=%lu\n", sizeof(b));

	logWs("冒泡排序 降序 begin\n");
    // 冒泡排序 降序
    //printf("冒泡排序 降序\n");
    bubbleSort(a, c, SortArrLen, funcDescend);
    for (int i=0; i<SortArrLen; ++i){
        printf("c%d->%d ",i, c[i]);
    }
    printf("\nsizeof(c)=%lu\n", sizeof(c));


    int d[SortArrLen], e[SortArrLen];
	logWs("快速排序 升序 begin\n");
    // 快速排序 升序
    //printf("快速排序 升序\n");
    quickSort(a, d, SortArrLen, funcAscend);
    for (int i=0; i<SortArrLen; ++i){
        printf("d%d->%d ",i, d[i]);
    }
    printf("\nsizeof(d)=%lu\n", sizeof(d));

    // 快速排序 降序
	logWs("快速排序 降序 begin\n");
    //printf("快速排序 降序\n");
    quickSort(a, e, SortArrLen, funcDescend);
    for (int i=0; i<SortArrLen; ++i){
        printf("e%d->%d ",i, e[i]);
    }
    logWs("sizeof(e)=%lu\n", sizeof(e));
}
